// Created by Acer on 2/22 022.
#ifndef ANDROIDARCHITECT02_AVL_H
#define ANDROIDARCHITECT02_AVL_H

#include <iostream>
#include <queue>
#include <android/log.h>

using namespace std;

template<class K, class V>
struct TreeNode {
public:
    TreeNode<K,V>* left  = NULL;
    TreeNode<K,V>* right = NULL;
    K key;
    V value;
    int height;// 当前树的高度

    // 复制一个点。避免pNode被销毁，找不到关联关系。
    TreeNode(TreeNode<K, V> *pNode) : height(1) { // 初始节点的高度为 1
        this->left = pNode->left;
        this->right = pNode->right;
        this->key = pNode->key;
        this->value = pNode->value;
    }

    TreeNode(K key, V value) : height(pNode->height) {
        this->right = NULL;
        this->left = NULL;
        this->key = key;
        this->value = value;
    }
};

template<class K, class V>
class AVL {
     TreeNode<K,V>* root; // 根节点
     int count; // 个数

public:
    BTS() { // 构造函数，析构函数
        root = NULL;
        count = 0;
    }
    ~BTS(){
    }

    // 新增/修改
    void put(K key, V value) {
        root = addNode(root, key, value);
    }
    V* get(K key){
        // TODO 1.是否包含，包含了采取查找。没包含就不查找
        // 2. 没找到返回V*， int *value = AVL->get(100); if(value==NULL) { ...}
        return NULL;
    }
    int size(){
        return count;
    }
    // 删除操作。
    void remove(K key) {
        // 分情况处理，移除非叶子节点，也要返回指针。
        root = removeNode(root, key);
    }

    bool contains(K key) { // 是否包含
       TreeNode<K, V> *node = root; // 拿到根节点

       while (node) {
           if (node->key == key) {
               return node->value; // 包含
           } else if (node->key > key) { // 大，进入左边子树
               node = node->left;
           } else { // 进入右边子树
               node = node->right;
           }
       }
       return false;
    }

    // 中序遍历
    void inOrderTraverse(void (*fun)(K, V)) {
        inOrderTraverse(root, fun);
    }
    // 层序遍历，借助queue队列实现。
    void levelTraverse(void (*fun)(K, V)) {
        if (root == NULL) {
            return;
        }
        TreeNode<K, V> *node = root;
        queue<TreeNode<K, V> *> nodes;
        nodes.push(node); // push 进去

        while (!nodes.empty()) { // 非空，不断地循环它
            node = nodes.front();
            fun(node->key, node->value); // 访问节点node，输出key-value
            nodes.pop(); // node弹出来

            if (node->left) { // 左边不为空，放进去
                nodes.push(node->left);
            }
            if (node->right) { // 右边不为空，放进去
                nodes.push(node->right);
            }
        }
    }


private:
    int getHeight(TreeNode<K, V> *pNode) {
        return pNode ? pNode->height : 0; // 节点为nil 值为0
    }
    // 四个旋转操作
    // 右旋，[插入3时右旋]
    TreeNode<K,V>* R_Rotation(TreeNode<K, V> *pNode){
        // 1.原来的 左孩子left变成 根节点。返回left
        TreeNode<K, V> *left = pNode->left;
        TreeNode<K, V> *right = left->right; // 记录一下原来left的right节点:避免被覆盖了
        left->right = pNode; // 2.原来的根节点，变为新根节点的 右节点；（左边不动）
        pNode->left = right; // 新节点的原来的 右节点，变成 被替换节点的左分支(左孩子)。（包括为空的情况。）
        // ** 新节点2 如果原来有右节点2.5，右旋时，原节点3的左节点 赋值为2.5。

        // 更新原来根节点的高度
        pNode->height = max(getHeight(pNode->left), getHeight(pNode->right)) +1;
        // 更新 新的根节点的高度
        left->height = max(getHeight(left->left), getHeight(left->right)) +1;
        return left; // 根节点，变为left
    }

    // 左旋（eg：4放上去，作为左节点，3作为做节点）
    TreeNode<K, V> *L_Rotation(TreeNode<K, V> *pNode) {
        TreeNode<K, V> *right = pNode->right;
        TreeNode<K, V> *left = pNode->left; // 记录一下:避免被覆盖了
        right->left = pNode; // 4的左边变成原来的父节点3（右边节点不动5）
        pNode->right = left; // 新根节点4的左节点(3.5)，赋值给3的右节点。(包括为空的情况)

        // 更新高度
        pNode->height = max(getHeight(pNode->left), getHeight(pNode->right)) + 1;
        right->height = max(getHeight(right->left), getHeight(right->right)) + 1;
        return right; // 根节点，变为right
    }

    // 先左旋，再右旋
    TreeNode<K, V> *L_R_Rotation(TreeNode<K, V> *pNode) {
        pNode->left = L_Rotation(pNode->left); // 先以左孩子为节点，做左旋操作。
        return R_Rotation(pNode); // 已当前节点，做右旋操作。
    }
    // 先右旋，再左旋
    TreeNode<K, V> *R_L_Rotation(TreeNode<K, V> *pNode) {
        pNode->right = R_Rotation(pNode->right); // 先对3节点右旋，形成123结构。
        return L_Rotation(pNode); // 在123的基础上，左旋形成213的结构。
    }


    // 返回新建的节点，与节点递归比较。
    TreeNode<K,V>* addNode(TreeNode<K,V>* pNode, K key, V value) {
        if(pNode == NULL) {
            count ++;
            return new TreeNode<K,V>(key, value); // 新建子节点（根节点 或叶子结点）
        }

        if(pNode->key > key){
            // 小。插入左边, 递归调用。返回的节点作为左子树。
            pNode->left = addNode(pNode->left, key, value);
            // 是否搭配了平衡规则。左边的层级 - 右边的层级 比较
            if(getHeight(pNode->left) - getHeight(pNode->right) == 2) {
                // 往左边增加，所以左边高度可能会增长  // 调整，右旋操作
                // 不能简单的就做一次右旋，有可能要先左旋再右旋。
                if(getHeight(pNode->left->right) > getHeight(pNode->left->left)) {
                    // 先左旋，再右旋
                     pNode = L_R_Rotation(pNode);
                } else {
                     // 仅仅右旋
                     pNode = R_Rotation(pNode);
                }

            }
        } else if(pNode->key < key){
            // 大：插入右边, 递归调用。返回的节点作为右子树。
            pNode->right = addNode(pNode->right, key, value);
            // 左旋
            if(getHeight(pNode->right) - getHeight(pNode->left) == 2) {
                if(getHeight(pNode->right->left) > getHeight(pNode->right->right)) {
                    // 先右旋，再左旋
                    pNode = R_L_Rotation(pNode);
                } else {
                    pNode = L_Rotation(pNode);
                }
            }
        } else {
            // key相等，替换值value
            pNode->value = value;
        }
        // 更新整个 二叉树的高度
        pNode->height = max(getHeight(pNode->left), getHeight(pNode->right)) + 1;
        return pNode;
    }




    // 删除节点
    TreeNode<K,V>* removeNode(TreeNode<K,V>* pNode, K key) {
        // 递归结束
        if(pNode == NULL) return NULL;

        if(pNode->key > key) { // 往左边删除
            pNode->left = removeNode(pNode->left, key);
            // 干掉了左边，只会把左边的点减少。右边的大于左边的
           if(getHeight(pNode->right) - getHeight(pNode->left) == 2) {
               if(getHeight(pNode->right->left) > getHeight(pNode->right->right)) {
                   // 先右旋，再左旋
                   pNode = R_L_Rotation(pNode);
               } else {
                   pNode = L_Rotation(pNode); // 左旋
               }
           }

        } else if(pNode->key < key) { // 往右边删除
            pNode->right = removeNode(pNode->right, key);
            if(getHeight(pNode->left) - getHeight(pNode->right) == 2) {
                // 往左边增加，所以左边高度可能会增长  // 调整，右旋操作
                // 不能简单的就做一次右旋，有可能要先左旋再右旋。
                if(getHeight(pNode->left->right) > getHeight(pNode->left->left)) {
                    // 先左旋，再右旋
                     pNode = L_R_Rotation(pNode);
                } else {
                     // 仅仅右旋
                     pNode = R_Rotation(pNode);
                }
            }

        } else { // key相等（找到了）。执行删除
            count --;
            if(pNode->left == NULL && pNode->right == NULL) { // 无叶子结点，左右都为空
                delete pNode;
                return NULL;
            } else if(pNode->right == NULL) {
                // 右边为空，把左边放上去。
                // 左节点不为空, 左边的比父节点小。可以直接将左节点 替代当前删除的节点。
                TreeNode<K,V>* left = pNode->left;
                delete pNode;
                return left; // 避免pNode被析构了，找不到left。
            } else if(pNode->left == NULL) { // 右节点不为空
                // 左边为空，把右边放上去。
                TreeNode<K,V>* right = pNode->right;
                delete pNode;
                return right;
            } else { // 左右子树，都不为空的情况。
                if(getHeight(pNode->left) > getHeight(pNode->right) ) {
                    // 去左边找一个node(最小的)
                    // 找一个节点代替它。让树继续满足二叉搜索树。
                    // 从左边找最大值来替代，或者从右边找最小值。缓存Node。
                    TreeNode<K,V>* maxNode = maximum(pNode->left);
                    TreeNode<K,V>* successor = new TreeNode<K, V>(maxNode);
                    // 原来的左节点，作为新根节点的左节点；原来的右节点，作为新根节点的右节点。
                    // 保证移除的子节点的高度，都有更新
                    successor->left = removeNode(pNode->left, maxNode->key); // 删除升级为根节点的 节点。
                    count++; // 并没有删除升级的点，所以此处count要 +1
                    successor->right = pNode->right;
                    delete (pNode); // 删除当前节点。
                    pNode = successor;
                    // 删除节点，要更新节点的高度。删除根节点或(左右子节点的情况)，不会去更新子节点的高度。
                } else { //去右边找一个代替，根节点。
                    TreeNode<K,V>* minNode = minimum(pNode->right);
                    TreeNode<K,V>* successor = new TreeNode<K, V>(minNode);
                    // 原来的左节点，作为新根节点的左节点；原来的右节点，作为新根节点的右节点。
                    // 保证移除的子节点的高度，都有更新
                    successor->right = removeNode(pNode->right, minNode->key); // 删除升级为根节点的 节点。
                    count++; // 并没有删除升级的点，所以此处count要 +1
                    successor->left = pNode->left;
                    delete (pNode); // 删除当前节点。
                    pNode = successor;
                }
            }
        }
        // 更新树的高度
        pNode->height = max(getHeight(pNode->left), getHeight(pNode->right)) + 1;
        return pNode;
    }

    //-------------------------------
    // 找右边的后进node(右边最小的)
    TreeNode<K,V>*  minimum(TreeNode<K,V>* pNode) {
        if(pNode->left == null) {
            return pNode; // 找到了
        }
        return minimum(pNode->left);
    }
    // 找左边的后进Node（左边树 最大的值）
    TreeNode<K,V>* maximum(TreeNode<K,V>* pNode) {
        // 不断地往右边找，直到找到右边为空的节点，就找到了最大值。
        if(pNode->right == null) {
            return pNode; // 找到了
        }
        return maximum(pNode->right); // 不断往右边找。
    }

    // 找到升级了的点，删除。
    TreeNode<K,V>* deleteMax(TreeNode<K,V>* pNode) {
        if(pNode->right == null) {
            // 保存左边分支。
            TreeNode<K,V>* left = pNode->left;
            delete (pNode); // 删除 升级的节点。
            count--;
            return left; // 被删除点，左边的分支。要保留。
        }
        // 不断地找，直到找到删除。
        pNode->right = deleteMax(pNode->right);
        return pNode;
    }

    // 中序遍历
    void inOrderTraverse(TreeNode<K, V> *pNode, void (*pFunction)(K, V)) {
        if (pNode == NULL) {
            return; // 到底了。
        }
        inOrderTraverse(pNode->left, pFunction); // 递归：先遍历左边
        pFunction(pNode->key, pNode->value);     // 访问自身
        inOrderTraverse(pNode->right, pFunction); // 遍历右边
    }

};

#endif //ANDROIDARCHITECT02_AVL_H
